数据结构 数组模拟队列与循环队列优化

队列介绍

队列是一个有序列表，可以用数组或是链表来实现。

遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

示意图：使用数组模拟队列示意图

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如上图，其中 maxSize 是该队列的最大容量。

因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear 则是随着数据输入而改变

入队列

当我们将数据存入队列时称为 addQueue，它的处理需要有两个步骤：

思路分析 将尾指针往后移：rear + 1

• 当 front == rear 时队列为空
• 若尾指针 rear 小于队列的最大下标 maxSize - 1，则将数据存入 rear 所指的数组元素中，否则无法存入数据
• 当 rear == maxSize - 1 时队列满

出队列

从队列里面出队的操作称为 deQueue，它的处理也大同小异：

思路分析 将头指针往后移：front + 1

• 当 front == rear 时队列为空

单向队列

使用数组模拟队列

public class MyQueue {

    private final int[] data;
    private final int maxSize;

    private int front;
    private int rear;

    public MyQueue(int size) {
        this.maxSize = size;
        this.data = new int[size];

        this.front = -1;
        this.rear = -1; // 因为每次插入都要先让 rear 移动一位再插入，所以最开始应该为 -1
    }

    //判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }

    public boolean add(int e) {
        if (isFull()) {
            return false;
        }
        data[++rear] = e; // 尾指针后移一位后插入
        return true;
    }


    public int remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("队列为空，无法取得数据");
        }
        return data[++front]; //
    }

    public static void main(String[] args) {
        MyQueue queue = new MyQueue(3);
        queue.add(100);
        queue.add(31);
        System.out.println(queue.remove()); // 100
    }
}

使用 List 集合模拟队列

使用 List 集合有个好处，就是无需考虑 rear 指针（因为 List 能自动扩容），只需要一个 front 指针表示当前头节点的位置

class MyQueue {
    // 存储元素
    private List<Integer> data;

    // 记录起始位置的指针
    private int front;
    
    public MyQueue() {
        data = new ArrayList<Integer>();
        front = 0;
    }

    /** 在队列中插入一个元素，如果操作成功则返回 true */
    public boolean addQueue(int x) {
        data.add(x);
        return true;
    };
    
    /** 从队列中删除元素，如果操作成功则返回 true 
     *  并不会真的删除元素，而是通过移动起始指针，来指示当前指向的第一个元素
     */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        front++; 
        return true;
    }
    
    /** 从队列中获取最前面的项 */
    public int Front() {
        return data.get(front);
    }

    /** 检查队列是否为空，当指针的位置已经到和队列大小一样大了就表示元素已经删完了 */
    public boolean isEmpty() {
        return front >= data.size();
    }
};

循环队列

但是上面这种 “单向队列” 的做法有个问题，就是并没有真正的删除，而是通过移动指针避开了这些删除的元素而已，随着起始指针的移动，浪费了越来越多的空间，当我们有空间限制时，这将是难以接受的。

对前面的数组模拟队列的优化，充分利用数组，因此将数组看做是一个环形的。（通过取模的方式来实现即可）

注意：不要小看这个循环队列，这里面还是有很多知识值得学习的，例如这里的取余机制，通过取余来获取一个不会大于 size 的索引，这个机制可以用来将索引置于头部

分析说明：

1、尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 时表示满

2、rear == front 时为空

3、分析示意图：

思路如下：

1、front 变量的含义做一个调整：front 就指向队列的第一个元素，也就是说 data[front] 就是队列的第一个元素。

front 的初始值等于 0

2、rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定。

rear 的初始值等于 0

3、当队列满时，条件是 (rear + 1) % maxsize == front

4、对队列为空的条件，rear== front

5、当我们这样分析，队列中有效的数据的个数为 (rear + maxSize - front) % maxSize

6、我们就可以在原来的队列上修改得到一个环形队列

public class MyCircularQueue {

    private final int[] data;
    private final int maxSize;

    private int front;
    private int rear;

    public MyCircularQueue(int size) {
        this.maxSize = size;
        this.data = new int[size];

        this.front = 0;
        this.rear = 0;
    }

    //判断队列是否满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    //判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }

    public boolean add(int e) {
        if (isFull()) {
            return false;
        }

        //直接将数据加入
        data[rear] = e;
        //将rear后移
        rear = (rear + 1) % maxSize;

        return true;
    }


    public int remove() {
        if (isEmpty()) {
            throw new NoSuchElementException("队列为空，无法取得数据");
        }

        int value = data[front];
        front = (front + 1) % maxSize;
        return value;
    }

}

Java 内置的队列

注意：实际上 LinkedList 实现的是双端队列 Deque 接口，只是 Deque 接口也继承了 Queue 接口而已

public class Main {
    public static void main(String[] args) {
        Queue<String> q = new LinkedList<>();
        // 添加3个元素到队列:
        q.offer("apple");
        q.offer("pear");
        q.offer("banana");
        // 队首永远都是 apple，因为 peek() 不会删除它:
        System.out.println(q.peek()); // apple
        System.out.println(q.peek()); // apple
        // 移除首元素并返回
        System.out.println(q.poll()); // apple
    }
}